package com.arron.algorithm.leetcodetop100.动态规划.子序列or子数组;

import com.arron.algorithm.leetcodetop100.前缀和.最大子数组和_前缀和;
import com.arron.algorithm.leetcodetop100.滑动窗口.最大子数组和;

/**
 * 53. 最大子数组和 ,
 *  @see  最大子数组和_前缀和
 *   @see 最大子数组和
 */
public class 最大子数组和_动态规划 {



    public int maxSubArray(int[] nums) {
        if (nums.length<2){
            return nums[0];
        }

        //dp[i] 代表以nums[i] 结尾的最大子数组和
        int[] dp = new int[nums.length];

        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            //想要最大，要么自己组成一个子数组，要么以i-1结尾最大的子数组和+自己
            dp[i] = Math.max(dp[i-1] +nums[i],nums[i]);

        }
        int maxSubSum = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            maxSubSum = Math.max(dp[i],maxSubSum);
        }
        return maxSubSum;
    }

    public static void main(String[] args) {
        最大子数组和_动态规划 maxArraySum = new 最大子数组和_动态规划();

        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxArraySum.maxSubArray(nums));

    }


}
